#include <iostream>
#include <list>
#include <cassert>
#include <unordered_map>
#include <map>

using namespace std;

class MemoryPool {
private:
    struct MemoryBlock {
        size_t size;
        bool isAllocated;
    };

    char* pool;
    std::map<char*, MemoryBlock> blocks;

public:
    MemoryPool(size_t totalSize) {
        pool = new char[totalSize];
        blocks[pool] = {totalSize, false};
    }

    ~MemoryPool() {
        delete[] pool;
    }

    char* allocate(size_t size) {
        for (auto& pair : blocks) {
            char* blockAddress = pair.first;
            MemoryBlock& block = pair.second;

            if (!block.isAllocated && block.size >= size) {
                if (block.size > size) {
                    // Split the block
                    char* newBlockAddress = blockAddress + size;
                    MemoryBlock newBlock = {block.size - size, false};
                    blocks[newBlockAddress] = newBlock;
                    block.size = size;
                }

                block.isAllocated = true;
                return blockAddress;
            }
        }

        throw std::bad_alloc();
    }

    void deallocate(char* blockAddress) {
        auto it = blocks.find(blockAddress);
        if (it == blocks.end() || !it->second.isAllocated) {
            throw std::invalid_argument("Invalid block address");
        }

        it->second.isAllocated = false;

        // Merge with next block if it's free
        auto nextIt = std::next(it);
        if (nextIt != blocks.end() && !nextIt->second.isAllocated) {
            it->second.size += nextIt->second.size;
            blocks.erase(nextIt);
        }

        // Merge with previous block if it's free
        if (it != blocks.begin()) {
            auto prevIt = std::prev(it);
            if (!prevIt->second.isAllocated) {
                prevIt->second.size += it->second.size;
                blocks.erase(it);
            }
        }
    }
};

int main() {
    MemoryPool pool(1024);

    char* block1 = pool.allocate(128);
    char* block2 = pool.allocate(256);
    char* block3 = pool.allocate(512);

    pool.deallocate(block2);
    pool.deallocate(block1);

    char* block4 = pool.allocate(256);
    assert(block4 == block1);

    cout << "All test cases passed!" << endl;

    return 0;
}